Theodora, theo Michael Grant, là hậu duệ của người Hy Lạp tại Síp.[3] Có nhiều ý kiến khác nhau về nơi sinh của bà. Theo Michael người Syria, bà sinh ra ở Mabbug, Syria;[4] Nicephorus Callistus Xanthopoulos cho rằng Theodora là người Síp bản địa, trong khi tuyển tập Patria được cho là của George Codinus, chỉ ra rằng Theodora đến từ Paphlagonia. Bà sinh vào khoảng năm 500 sau công nguyên.

Cha bà, Acacius, là một người huấn luyện gấu của phe Xanh môn Đua xe ngựa, loại hình thể thao phổ biến nhất thời bấy giờ ở Constantinople. Mẹ bà có tên không được ghi lại, là một vũ công và một nữ diễn viên.[5] Bố mẹ bà còn có hai người con gái nữa.[6] Sau khi người cha mất khi Theodora lên bốn,[7] mẹ bà đã đem các con tới trường đua ngựa để cố vũ cho phe Xanh. Từ đó trở đi Theodora trở thành người ủng hộ phe Xanh.

Procopius (trong cuốn Bí sử của mình) kể rằng Theodora từ khi còn nhỏ đã theo gương của chị gái Komito và làm việc trong một nhà thổ bình dân tại Constantinople; sau đó bà trở thành người biểu diễn trên sân khấu.[8] Theodora, trong lời kể của Procopius, đã làm nên tên tuổi bằng vai diễn trong vở Leda và chim thiên nga.[9] Công việc của một nữ diễn viên vào thời điểm bấy giờ thường bao gồm cả những buổi "triển lãm không đứng đắn trên sân khấu" và cung cấp dịch vụ tình dục ngoài sân khấu.

Trong thời gian này, bà đã gặp người vợ tương lai của Belisarius, Antonina, người sau này trở thành một mệnh phụ trong triều đình của Theodora.

Vào năm 16 tuổi, bà tới Bắc Phi cùng với một quan chức Syria tên là Hecebolus khi ông đến Libyan Pentapolis để nhậm chức thống đốc.[10] Bà ở với ông ta gần bốn năm trước khi trở về Constantinople. Bị bỏ rơi và bị ngược đãi bởi Hecebolus, trên đường trở về thủ đô, bà đã định cư một thời gian tại Alexandria, Ai Cập. Bà được cho là đã gặp Thượng phụ Timothy III tại Alexandria, người theo Hiệp tính thuyết, tại thời điểm đó bà đã cải đạo sang Cơ đốc giáo Hiệp tính. Từ Alexandria, bà đến Antioch và gặp một vũ công của phe Xanh, Macedonia, người có lẽ là một người đưa tin cho Justinian.

Bà trở lại Constantinople vào năm 522 và theo John người Ephesus, bà đã từ bỏ lối sống trước đây và làm việc như một người quay len trong một ngôi nhà gần cung điện. Tuy nhiên, tính cực đoan và bảo thủ trong giọng văn ẩn dụ tiêu cực của Procopius và lối văn ẩn dụ tích cực của John người Ephesus đã khiến hầu hết các học giả kết luận rằng tính chính xác của cả hai nguồn đều khả nghi.

Justinian gặp khó khăn khi tìm cách kết hôn với Theodora. Ông là người thừa kế ngai vàng của chú mình, Hoàng đế Justin I và một đạo luật La Mã từ thời Constantine ngăn cản bất cứ ai thuộc cấp nguyên lão kết hôn với các nữ diễn viên. Năm 525, Justin bãi bỏ đạo luật này và Justinian kết hôn với Theodora.[10] Đến thời điểm này, bà đã có một người con gái (tên không rõ). Justinian rõ ràng đối xử với người con gái này và cả con trai của cô là Athanasius như những hậu duệ chính thống,[11] mặc dù các nguồn tin không thống nhất về việc liệu Justinian có phải là cha đẻ của người con gái hay không.